import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public  class Main {


      public  class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
     }

    class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            if(root == null){
                return new ArrayList<>();
            }
            List<Integer> list = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            TreeNode top = null;
            TreeNode prev = null;
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                top = stack.peek();

                if (top.right == null || top.right == prev) {
                    stack.pop();
                    list.add(top.val);
                    prev = top;//当前这个节点被打印了
                }else {
                    cur = top.right;
                }
            }
            return list;
        }
    }
}
